1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for substantially automating the computation of an alternate circuit path, which corresponds to a primary circuit path, given specified constraints.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
To address the demand for data communication services, the use of optical networks, such as a synchronous optical network (SONET) is becoming more prevalent. One type of SONET network, or one type of network that is subject to SONET standards, is a time division multiple access (TDM) network. TDM networks generally allocate single channels or lines to be used amongst multiple users, or customers of data communication services. The single channels may each be divided into slots of time during which each user has access to the single channels. Many TDM networks may be configured to include a path protected mesh network (PPMN). A PPMN is a mesh of unprotected links with substantially no physical topological constraint. One example of a PPMN is a unidirectional path-switched ring (UPSR), which is effectively a PPMN with a ring-like topology. A UPSR or a virtual UPSR in a PPMN, as will be appreciated by those skilled in the art, provides for two different paths between a source and a destination. The source and the destination each select traffic from one of the paths based upon, for example, signal presence and signal quality.
Although a network such as a TDM network is generally designed to ensure that information may be transferred within the network reliably, there are times where network components may fail. Failures of network components may cause received signals to have a relatively high bit-error rate or, in some cases, cause a signal to be completely lost. In SONET, mechanical failures and equipment failures may occur. Mechanical failures include the effects of vibrations which affect optical connections, and bends in links or fibers which may result in degraded signal levels. Equipment failures a may include, but are not limited to, failures of lasers which transmit optical signals, failures of links or channels over which signals are transmitted, and failures of nodes which are interconnected by links.
In order to compensate for link failures, links may be protected. A protected link is a link which has two fibers or cables over which signals may be transmitted substantially simultaneously. One example of a protected link is a link with “1+1” protection, as shown in FIG. 1a. A link 104 with 1+1 protection, i.e., a protected link, is a link between two nodes 108 that is made up of two unprotected links 106, i.e., sub-links. When an optical signal is to be transferred across protected link 104, the optical signal is transferred across both sub-links 106. That is, the optical signal is transferred redundantly across both sub-links 106. The use of two sub-links 106 within protected link 104 enables a choice to be made regarding which optical signal received on node 108b is to be accepted by node 108b. Typically, the signal with the lower bit-error rate is accepted.
Some links between nodes are unprotected as it is generally less expensive to transfer signals across an unprotected link than it is to transfer signals across a protected link. As shown in FIG. 1b, nodes 118 are in communication across an unprotected link 114. While an unprotected link 114 typically enables data to be transferred successfully, if unprotected link 114 fails, then there is no alternate link over which data may be transferred between nodes 118.
In general, nodes may have many links therebetween. FIG. 1c is a diagrammatic representation of nodes that are connected by both a protected link and an unprotected link, e.g., in a mixed protection domain. Nodes 128 are connected by a protected link 124a and an unprotected link 124b. As discussed above with respect to FIG. 1a, protected link 124a may include two unprotected sub-links. In some cases, when no protection is desired, unprotected link 124b may be used to transfer data between nodes 128. When a protected path is desired, protected link 124a may be used to route a data signal. As protected link 124a has 1+1 protection, if one of the sub-links in protected link 124a fails, the signal may still be transmitted over the other sub-link of protected link 124a. 
As previously mentioned, protected links and/or multiple links may be implemented between two nodes to protect against link failures, i.e., to prevent a link failure from causing a signal to be completely lost. In other words, a redundant scheme of links allows the reliability of an overall network to be improved. However, a redundant scheme of links does not compensate for node failures.
FIG. 2a is a diagrammatic representation of a TDM network which includes nodes and links. Within a TDM network 204, if a signal is to be transmitted between a source node B 208b and a destination node E 208e, a customer may specify to a network administrator whether he prefers a protected path or an unprotected path. If a protected path is requested, then protected links 212 may be used to for a protected path. Alternatively, if a customer wants a protected circuit that uses unprotected links, than a virtual UPSR in a PPMN, e.g., a primary path and an alternate path that form a ring-like UPSR at a circuit level, may be used. If the cost of transferring information across protected links 212 is more than that of transferring information across unprotected links 216, then a customer may decide whether to incur the additional cost associated with protected links 212, or to use unprotected links 216.
Typically, when a protected path is desired between source node B 208b and destination node E 208e, if protected links are available, the protected links are selected for inclusion in a path. However, when protected links such as links 212 are unavailable for use, e.g., when there is no available bandwidth on links 212, a least switched unprotected path between source node B 208b and destination node E 208e which has a corresponding alternate path is desired. In other words, a path which uses the fewest number of nodes 208, which function as switches, to reach destination node E 208e and has a corresponding alternate path is preferred when protected links 212 are unavailable. Such a path is generally considered to be the shortest available path between node B 208b and node E 208e. Hence, although an unprotected path from source node B 208b to destination node E 208e is also available using unprotected links 220, as well as through unprotected links 224, the use of unprotected links 216 is preferred. It should be understood, however, that if enough bandwidth is not available in the path through links 216, paths through either links 220 or links 224 may be used instead.
If a path through links 216 is a primary circuit path or, more specifically, a segment of a primary circuit path that exists between node B 208b and node E 208e, then an alternate circuit path may be defined between node B 208b and node E 208e to protect against failures associated with the primary circuit path. For instance, an alternate circuit path between node B 208b and node E 208e may be defined through links 220 and one link 216 which connects node D 208d and node E 208e. 
Although the alternate circuit path through links 220, in cooperation with link 216 between node D 208d and node E 208e is generally suitable, in order to maintain link diversity, an alternate circuit path through links 224 is more suitable. An alternate circuit path that uses links 220 does not comply with a link diverse constraint, since a failure of link 216 between nodes D 208d and node E 208e would result in a failure of both the primary circuit path and the alternate circuit path.
An alternate circuit path that uses links 224 is also suitable for use if network 204 requires a nodal diverse constraint, since no nodes 208, other than source node B 208b and destination node E 208e, are shared between the primary circuit path and the alternate circuit path that uses links 224. Hence, if one of node C 208c or node D 208d suffers a failure, the alternate circuit path would not be affected.
As will be appreciated by those skilled in the art, some links between nodes may be tunnels, e.g., VT tunnels. A tunnel is typically a bigger traffic or circuit pipe between two nodes with intermediate nodes switching at the bigger pipe level without looking at the pipe. Future traffic that is compatible with the pipe may be routed through a tunnel. FIG. 2b is a diagrammatic representation of a tunnel. A tunnel 254 includes XCVT points 256, and enables traffic, as for example VT traffic, to be passed therethrough. Tunnel 254 is generally linked to nodes 260 such that signals may be transmitted from node 260b to node 260c through tunnel 254. However, nodes 260 are not aware of how many internal nodes 264 exist as a part of tunnel 254. In general, an alternate tunnel for traffic may be needed to compensate for a failure of either or both internal nodes 264 of tunnel 254 or internal links 266 of tunnel 254.
The process of creating an alternate circuit path within a TDM network that is either nodal diverse or link diverse is often needed, as overall protected circuits, or circuits with path redundancy, are often requested, e.g., by network customers. In addition to creating circuit paths that are nodal diverse or link diverse, SONET standards, as previously mentioned, specify that a UPSR may not have any network links that are protected. Hence, to create an alternate circuit path within a TDM network that includes a UPSR and is subject to a nodal diverse constraint, all nodes included in a primary circuit path, along with all protected links, must be identified and eliminated from a routing process. Protected links are removed from consideration to prevent nested protection domains. Conventionally, a network administrator must manually specify an alternate circuit path that does not include nodes associated with a primary circuit path or protected links, which is often time consuming and tedious, especially when a TDM network is large and complex. Likewise, for a TDM network that is subject to a link diverse constraint, the network administrator must manually specify an alternate circuit path that does not include either protected links or links which were used to create the alternate circuit path. In addition to being a time consuming process, manually specifying an alternate circuit path may result in a node associated with a primary circuit path, a link associated with the primary circuit path, or a protected link being inadvertently included in the alternate circuit path due to human error.
Therefore, what is needed is an efficient method and apparatus for creating alternate circuit paths which correspond to primary circuit paths. That is, what is desired is an efficient and accurate system which enables alternate circuit paths which are either nodal diverse or link diverse, and do not include protected links, to be created.